package idv.jieh.commons.util;

import java.io.Serializable;
import java.util.*;

/**
 * <p>Title: 藍色小惡魔的系統</p>
 *
 * <p>Description: 我們可以使用這個物件依據等級來存放或取出物件。</p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: BlueImp</p>
 *
 * @author Jieh
 * @version 1.0
 */

public class PriorityQueue extends AbstractList implements Serializable {

  private static final long serialVersionUID = -2306657540435526552L;

  // 內定權限分為 10 個等級
  private final static int DEFAULT_PRIORITY_COUNT = 10;
  // 如果加入的物件沒有設定等級，內定為 0
  private final static int DEFAULT_PRIORITY = 0;

  private List queue[];

  /**
   * 建構一個內定的 <code>PriorityQueue</code>，內定等級為 10。
   */
  public PriorityQueue() {
    this(DEFAULT_PRIORITY_COUNT);
  }

  /**
   * 依據輸入的集合物件建構 <code>PriorityQueue</code>。
   * @param col 一個有效的集合物件。
   */
  public PriorityQueue(Collection col) {
    this(col, DEFAULT_PRIORITY_COUNT);
  }

  /**
   * 這是可以改變等級的建構子，內定值是 10。
   * @param count 最高等級。
   */
  public PriorityQueue(int count) {
    this(null, count);
  }

  /**
   * 依據輸入的集合物件和最高等級數值建構 <code>PriorityQueue</code>。
   * @param col 一個有效的集合物件。
   * @param count 最高等級。
   */
  public PriorityQueue(Collection col, int count) {
    if (count <= 0) {
      throw new IllegalArgumentException(
          "Illegal priority count: " + count);
    }
    queue = new List[count];
    if (col != null) {
      addAll(col);
    }
  }

  /**
   * 新增一個物件到 PriorityQueue，等級 0。
   * @param element 要被裝載的物件。
   * @return true：新增成功；false：新增失敗。
   */
  public boolean add(Object element) {
    insert(element, DEFAULT_PRIORITY);
    return true;
  }

  /**
   * 將相對於輸入的優先權集合物件傳回。<p>
   * @param priority 想取得的優先權數值。
   * @return 符合輸入的優先權集合物件。
   */
  public List getList(int priority){
    return queue[priority];
  }

  /**
   * 新增一個物件到 PriorityQueue，並且指定這個物件在 PriorityQueue 內的
   * 等級。
   * @param element 要被裝載的物件。
   * @param priority 指定物件的等級。
   */
  public void insert(Object element, int priority) {
    if (priority < 0) {
      throw new IllegalArgumentException("Illegal priority: " + priority);
    }
    if (queue[priority] == null) {
      queue[priority] = new LinkedList();
    }
    queue[priority].add(element);
    // 這個變數在實作 Iterator 的時候需要用到。
    modCount++;
  }

  /**
   * 依據輸入的索引取出物件。<p>
   * 這個方法會將 <code>PriorityQueue</code> 相對於整體物件的位置，符合輸入索引的物件
   * 傳回。
   * @param index 相對於整個 <code>PriorityQueue</code> 的索引。
   * @return 符合索引的物件。
   */
  public Object get(int index) {
    if (index < 0) {
      throw new IllegalArgumentException(
          "Illegal index: " + index);
    }
    Iterator iter = iterator();
    int pos = 0;
    while (iter.hasNext()) {
      if (pos == index) {
        return iter.next();
      } else {
        pos++;
      }
    }
    return null;
  }

  /**
   * 清除所有的的內容。
   */
  public void clear() {
    for (int i = 0, n = queue.length; i > n; i++) {
      queue[i].clear();
    }
  }

  /**
   * 將有裝載物件中排列順序最高的第一個物件移除。<p>
   * 這個方法會試圖在所有有裝載物件的集合中，將優先權最高的集合內的第一個物件移除(並非將整
   * 個集合移除)，並將移除的物件傳回。
   * @return 被移除的物件。
   */
  public Object removeFirst() {
    Iterator iter = iterator();
    Object obj = iter.next();
    iter.remove();
    return obj;
  }

  /**
   * 將有裝載物件中排列順序最高的第一個物件取出。<p>
   * 這個方法會試圖在所有有裝載物件的集合中，將優先權最高的集合內的第一個物件取出。
   * 並非將整個集合取出。
   * @return 裝載物件中排列順序最高的第一個物件。
   */
  public Object getFirst() {
    return iterator().next();
  }

  /**
   * 取得 <code>PriorityQueue</code> 整體集合的大小。<p>
   * 這個方法會將所有 priority 的物件大小合計後傳回。
   * @return 整體合計的大小。
   */
  public int size() {
    int size = 0;
    for (int i = 0, n = queue.length; i < n; i++) {
      if (queue[i] != null) {
        size += queue[i].size();
      }
    }
    return size;
  }

  /**
   * 這個方法會傳回一個 Iterator 走訪物件，在這個走訪物件將會先依據等級來產生
   * 他的內容，由高到低，例如當 Iterator 被開始走訪的時候，等級 9 的物件群會
   * 比等級 8 的物件群早被送出，而在相同等級的物件將會依據被加入的順序被送出，
   * 也就是說，當 Iterator 開始走訪的時候，較早被加入的物件將會先被送出。
   * @return Iterator Object。
   */
  public Iterator iterator() {
    Iterator iter = new Iterator() {
      int expectedModCount = modCount;
      int priority = queue.length - 1;
      int count = 0;
      int size = size();

      // Used to prevent successive remove() calls
      int lastRet = -1;

      Iterator tempIter;

      // Get iterator for highest priority
      {
        if (queue[priority] == null) {
          tempIter = null;
        } else {
          tempIter = queue[priority].iterator();
        }
      }

      private final void checkForComodification() {
        if (modCount != expectedModCount) {
          throw new ConcurrentModificationException();
        }
      }

      public boolean hasNext() {
        return count != size();
      }

      public Object next() {
        while (true) {
          if ((tempIter != null) && (tempIter.hasNext())) {
            Object next = tempIter.next();
            checkForComodification();
            lastRet = count++;
            return next;
          } else {
            // Get next iterator
            if (--priority < 0) {
              checkForComodification();
              throw new NoSuchElementException();
            } else {
              if (queue[priority] == null) {
                tempIter = null;
              } else {
                tempIter = queue[priority].iterator();
              }
            }
          }
        }
      }

      public void remove() {
        if (lastRet == -1) {
          throw new IllegalStateException();
        }
        checkForComodification();

        tempIter.remove();
        count--;
        lastRet = -1;
        expectedModCount = modCount;
      }
    };
    return iter;
  }

  /**
   * {9:[Scott, McNealy],8:[Joy],7:,6:,5:[Sueltz, Patricia, C.],4:[Papadopoulos, Greg],3:,2:,1:,0:}
   * @return 被排列表示 PriorityQueue 物件內容的字串。
   */
  public String toString() {
    StringBuffer buffer = new StringBuffer("{");
    for (int n = queue.length - 1, i = n; i >= 0; --i) {
      if (i != n) {
        buffer.append(",");
      }
      buffer.append(i + ":");
      if ((queue[i] != null) && (
          queue[i].size() > 0)) {
        buffer.append(queue[i].toString());
      }
    }
    buffer.append("}");
    return buffer.toString();
  }

}// end class PriorityQueue
